#define  _CRT_SECURE_NO_WARNINGS 1
#include <iostream>


namespace ghs
{
	template<class T>
	struct ListNode
	{
		typedef ListNode<T> Node;
		Node* _prev;
		Node* _next;
		T _val;

		ListNode(const T& t = T())
			:_prev(nullptr),
			_next(nullptr),
			_val(t)
		{
		}
	};

	template<class T>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		Node* _node;

		ListIterator(Node* node)
			:_node(node)
		{
		}

		//++it
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//--it
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//it++
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		//it--
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		T& operator*()
		{
			return _node->_val;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}
	};

	template<class T>
	class List
	{
		typedef ListNode<T> Node;
	public:
		typedef ListIterator<T> iterator;

		List()
			:_head(new Node)
		{
			_head->_prev = _head;
			_head->_next = _head;
		}
		void insert(iterator pos, const T& t)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(t);

			newnode->_next = cur;
			cur->_prev = newnode;
			newnode->_prev = prev;
			prev->_next = newnode;
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;
			return iterator(next);
		}

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head);
		}

		void push_back(const T& t)
		{
			insert(end(), t);
		}

		void push_front(const T& t)
		{
			insert(begin(), t);
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}
		
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		~List()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

	private:
		Node* _head;
	};

	void testlist()
	{
		List<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);

		/*for (auto e : lt)
		{
			std::cout << e << " ";
		}*/
		ListIterator<int> it = lt.begin();
		while (it != lt.end())
		{
			std::cout << *it << " ";
			it++;
		}
		std::cout << std::endl;
		lt.push_front(5);
		lt.push_front(6);
		lt.push_front(7);
		lt.push_front(8);
		for (auto e : lt)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		lt.pop_back();
		for (auto e : lt)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;

		lt.pop_front();
		for (auto e : lt)
		{
			std::cout << e << " ";
		}
		std::cout << std::endl;
	}
}